#include <iostream>

constexpr long MOD = 1000000007;
class Solution {
  public:
    int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        long result = 0;
        if (n % 3 == 0) result = pow(3, n / 3);
        if (n % 3 == 1) result = 4 * pow(3, (n - 4) / 3);
        if (n % 3 == 2) result = 2 * pow(3, (n - 2) / 3);
        return result % MOD;
    }

    long pow(int a, int n) {  // return a^n % 1000000007
        if (n == 0) return 1;
        if (n == 1) return a;
        long result = 1;
        result = pow(a, n / 2) % MOD;
        result *= result;
        if (n % 2 == 1) result *= a;
        return result % MOD;
    }
};
